home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 111_01 / tr2.c < prev    next >
Text File  |  1985-08-19  |  13KB  |  467 lines
  1. /*
  2. HEADER:        ;
  3. TITLE:        Squeezer;
  4. DESCRIPTION:    "Auxiliary file for the SQ.C and USQ.C package.
  5.         See SQUEEZER.DOC.";
  6. SYSTEM:        CP/M-80;
  7. FILENAME:    TR2.C;
  8. SEE-ALSO:    SQUEEZER.DOC;
  9. AUTHORS:    Dick Greenlaw;
  10. COMPILERS:    BDS C;
  11. */
  12. #include <bdscio.h>
  13. #include <dio.h>
  14. #include "sqcom.h"
  15. #include "sq.h"
  16. #define STDERR 4    /* error stream - always console */
  17.  
  18. /******** Second translation - bytes to variable length bit strings *********/
  19.  
  20.  
  21. /* This translation uses the Huffman algorithm to develop a
  22.  * binary tree representing the decoding information for
  23.  * a variable length bit string code for each input value.
  24.  * Each string's length is in inverse proportion to its
  25.  * frequency of appearance in the incoming data stream.
  26.  * The encoding table is derived from the decoding table.
  27.  *
  28.  * The range of valid values into the Huffman algorithm are
  29.  * the values of a byte stored in an integer plus the special
  30.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  31.  *
  32.  * The "node" array of structures contains the nodes of the
  33.  * binary tree. The first NUMVALS nodes are the leaves of the
  34.  * tree and represent the values of the data bytes being
  35.  * encoded and the special endfile, SPEOF.
  36.  * The remaining nodes become the internal nodes of the tree.
  37.  *
  38.  * In the original design it was believed that
  39.  * a Huffman code would fit in the same number of
  40.  * bits that will hold the sum of all the counts.
  41.  * That was disproven by a user's file and was a rare but
  42.  * infamous bug. This version attempts to choose among equally
  43.  * weighted subtrees according to their maximum depths to avoid
  44.  * unnecessarily long codes. In case that is not sufficient
  45.  * to guarantee codes <= 16 bits long, we initially scale
  46.  * the counts so the total fits in an unsigned integer, but
  47.  * if codes longer than 16 bits are generated the counts are
  48.  * rescaled to a lower ceiling and code generation is retried.
  49.  */
  50.  
  51. /* Initialize the Huffman translation. This requires reading
  52.  * the input file through any preceding translation functions
  53.  * to get the frequency distribution of the various values.
  54.  */
  55.  
  56. init_huff(ib)
  57. struct _buf *ib;
  58. {
  59.     int c, i;
  60.     int btlist[NUMVALS];    /* list of intermediate binary trees */
  61.     int listlen;        /* length of btlist */
  62.     unsigned *wp;    /* simplifies weight counting */
  63.     unsigned ceiling;    /* limit for scaling */
  64.  
  65.     /* Initialize tree nodes to no weight, no children */
  66.     init_tree();
  67.  
  68.     /* Build frequency info in tree */
  69.     do {
  70.         c = getcnr(ib);
  71.         if(c == EOF)
  72.             c = SPEOF;
  73.         if(*(wp = &node[c].weight) !=  MAXCOUNT)
  74.             ++(*wp);
  75.     } while(c != SPEOF);
  76.  
  77.     pcounts();    /* debugging aid */
  78.  
  79.     ceiling = MAXCOUNT;
  80.  
  81.     do {    /* Keep trying to scale and encode */
  82.         if(ceiling != MAXCOUNT)
  83.             printf("*** rescaling ***, ");
  84.         scale(ceiling);
  85.         ceiling /= 2;    /* in case we rescale */
  86.         pcounts();    /* debugging aid */
  87.  
  88.         /* Build list of single node binary trees having
  89.          * leaves for the input values with non-zero counts
  90.          */
  91.         for(i = listlen = 0; i < NUMVALS; ++i)
  92.             if(node[i].weight != 0) {
  93.                 node[i].tdepth = 0;
  94.                 btlist[listlen++] = i;
  95.             }
  96.  
  97.         /* Arrange list of trees into a heap with the entry
  98.          * indexing the node with the least weight at the top.
  99.          */
  100.         heap(btlist, listlen);
  101.  
  102.         /* Convert the list of trees to a single decoding tree */
  103.         bld_tree(btlist, listlen);
  104.  
  105.         /* Initialize the encoding table */
  106.         init_enc();
  107.  
  108.         /* Try to build encoding table.
  109.          * Fail if any code is > 16 bits long.
  110.          */
  111.     } while(buildenc(0, dctreehd) == ERROR);
  112.     phuff();    /* debugging aid */
  113.  
  114.     /* Initialize encoding variables */
  115.     cbitsrem = 0;    /*force initial read */
  116.     curin = 0;    /*anything but endfile*/
  117. }
  118.  
  119. /* The count of number of occurrances of each input value
  120.  * have already been prevented from exceeding MAXCOUNT.
  121.  * Now we must scale them so that their sum doesn't exceed
  122.  * ceiling and yet no non-zero count can become zero.
  123.  * This scaling prevents errors in the weights of the
  124.  * interior nodes of the Huffman tree and also ensures that
  125.  * the codes will fit in an unsigned integer. Rescaling is
  126.  * used if necessary to limit the code length.
  127.  */
  128.  
  129. scale(ceil)
  130. unsigned ceil;    /* upper limit on total weight */
  131. {
  132.     int c, ovflw, divisor, i;
  133.     unsigned w, sum;
  134.     char increased;        /* flag */
  135.  
  136.     do {
  137.         for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
  138.             if(node[i].weight > (ceil - sum))
  139.                 ++ovflw;
  140.             sum += node[i].weight;
  141.         }
  142.  
  143.         divisor = ovflw + 1;
  144.  
  145.         /* Ensure no non-zero values are lost */
  146.         increased = FALSE;
  147.         for(i = 0; i < NUMVALS; ++i) {
  148.             w = node[i].weight;
  149.             if (w < divisor && w > 0) {
  150.                 /* Don't fail to provide a code if it's used at all */
  151.                 node[i].weight = divisor;
  152.                 increased = TRUE;
  153.             }
  154.         }
  155.     } while(increased);
  156.  
  157.     /* Scaling factor choosen, now scale */
  158.     if(divisor > 1)
  159.         for(i = 0; i < NUMVALS; ++i)
  160.             node[i].weight /= divisor;
  161. }
  162.  
  163. /* heap() and adjust() maintain a list of binary trees as a
  164.  * heap with the top indexing the binary tree on the list
  165.  * which has the least weight or, in case of equal weights,
  166.  * least depth in its longest path. The depth part is not
  167.  * strictly necessary, but tends to avoid long codes which
  168.  * might provoke rescaling.
  169.  */
  170.  
  171. heap(list, length)
  172. int list[], length;
  173. {
  174.     int i;
  175.  
  176.     for(i = (length - 2) / 2; i >= 0; --i)
  177.         adjust(list, i, length - 1);
  178. }
  179.  
  180. /* Make a heap from a heap with a new top */
  181.  
  182. adjust(list, top, bottom)
  183. int list[], top, bottom;
  184. {
  185.     int k, temp;
  186.  
  187.     k = 2 * top + 1;    /* left child of top */
  188.     temp = list[top];    /* remember root node of top tree */
  189.     if( k <= bottom) {
  190.         if( k < bottom && cmptrees(list[k], list[k + 1]))
  191.             ++k;
  192.  
  193.         /* k indexes "smaller" child (in heap of trees) of top */
  194.         /* now make top index "smaller" of old top and smallest child */
  195.         if(cmptrees(temp, list[k])) {
  196.             list[top] = list[k];
  197.             list[k] = temp;
  198.             /* Make the changed list a heap */
  199.             adjust(list, k, bottom); /*recursive*/
  200.         }
  201.     }
  202. }
  203.  
  204. /* Compare two trees, if a > b return true, else return false
  205.  * note comparison rules in previous comments.
  206.  */
  207.  
  208. char    /* Boolean */
  209. cmptrees(a, b)
  210. int a, b;    /* root nodes of trees */
  211. {
  212.     if(node[a].weight > node[b].weight)
  213.         return TRUE;
  214.     if(node[a].weight == node[b].weight)
  215.         if(node[a].tdepth > node[b].tdepth)
  216.             return TRUE;
  217.     return FALSE;
  218. }
  219.  
  220. /* HUFFMAN ALGORITHM: develops the single element trees
  221.  * into a single binary tree by forming subtrees rooted in
  222.  * interior nodes having weights equal to the sum of weights of all
  223.  * their descendents and having depth counts indicating the
  224.  * depth of their longest paths.
  225.  *
  226.  * When all trees have been formed into a single tree satisfying
  227.  * the heap property (on weight, with depth as a tie breaker)
  228.  * then the binary code assigned to a leaf (value to be encoded)
  229.  * is then the series of left (0) and right (1)
  230.  * paths leading from the root to the leaf.
  231.  * Note that trees are removed from the heaped list by
  232.  * moving the last element over the top element and
  233.  * reheaping the shorter list.
  234.  */
  235.  
  236. bld_tree(list, len)
  237. int list[];
  238. int len;
  239. {
  240.     int freenode;        /* next free node in tree */
  241.     int lch, rch;        /* temporaries for left, right children */
  242.     struct nd *frnp;    /* free node pointer */
  243.     int i;
  244.  
  245.     /* Initialize index to next available (non-leaf) node.
  246.      * Lower numbered nodes correspond to leaves (data values).
  247.      */
  248.     freenode = NUMVALS;
  249.  
  250.     while(len > 1) {
  251.         /* Take from list two btrees with least weight
  252.          * and build an interior node pointing to them.
  253.          * This forms a new tree.
  254.          */
  255.         lch = list[0];    /* This one will be left child */
  256.  
  257.         /* delete top (least) tree from the list of trees */
  258.         list[0] = list[--len];
  259.         adjust(list, 0, len - 1);
  260.  
  261.         /* Take new top (least) tree. Reuse list slot later */
  262.         rch = list[0];    /* This one will be right child */
  263.  
  264.         /* Form new tree from the two least trees using
  265.          * a free node as root. Put the new tree in the list.
  266.          */
  267.         frnp = &node[freenode];    /* address of next free node */
  268.         list[0] = freenode++;    /* put at top for now */
  269.         frnp->lchild = lch;
  270.         frnp->rchild = rch;
  271.         frnp->weight = node[lch].weight + node[